// 一维数组中的前綴和

class NumArray
{
private:
	// 前綴和数组
	vector<int> preSum;

public:
	/*输入一个数组，构造前綴和*/
	NumArray(vector<int>& nums)
	{
		// preSum[0] = 0;便于计算累加和
		preSum.resize(nums.size() + 1); // resize():开空间+初始化

		// 计算 nums 的累加和
		for(int i = 1; i < preSum.size(); i++)
		{
			preSum[i] = preSum[i - 1] + num[i - 1];
		}
	}

	/*查询闭区间 [left, right] 的累加和*/
	int sumRange(int left, int right)
	{
		return preSum[right + 1] - preSum[left];
	}
};


// 区域和检索 - 数组不可变
class NumArray {

private:
    // 前綴和数组
    vector<int> preSum;

public:
    NumArray(vector<int>& nums) 
    {
        preSum.resize(nums.size() + 1);

        for(int i = 1; i < preSum.size(); i++)
        {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    
    int sumRange(int left, int right) 
    {
        return preSum[right + 1] - preSum[left];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */


// 二位矩阵中的前綴和
class NumMatrix
{
private:
	// 定义：preSum[i][j]记录matrix中子矩阵[0, 0, i - 1, j - 1]的元素和
	vector<vector<int>> preSum;

public:
	NumMatrix(vector<vector<int>>& matrix)
	{
		int m = matrix.size(), n = matrix[0].size();
		if(m == 0 || n == 0) return;

		// 构造前綴和矩阵
		preSum = vector<vector<int>> (m+1, vector<int>(n+1));
		for(int i = 1; i <= m; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				// 计算每个矩阵[0,0,i,j]
				preSum[i][j] = preSum[i-1][j]+preSum[i][j-1]+matrix[i-1][j-1]-preSum[i-1][j-1];
			}
		}
	}

	// 计算子矩阵[x1,y1,x2,y2]的元素和
	int sumRegion(int x1, int y1, int x2, int y2)
	{
		// 目标矩阵之和有四个相邻矩阵运算获得
		return preSum[x2+1][y2+1]-preSum[x1][y2+1]-preSum[x2+1][y1]+preSum[x1][y1];
	}
};



// 区域和检索 - 数组不可变
class NumArray {

private:
    vector<int> preSum; // 前缀和数组

public:
    NumArray(vector<int>& nums) 
    {
        preSum.resize(nums.size() + 1);

        for(int i = 1; i < preSum.size(); i++)
        {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    
    int sumRange(int left, int right) 
    {
        return preSum[right + 1] - preSum[left];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */


// 二维区域和检索 - 矩阵不可变
class NumMatrix {

private:
    // preSum[i][j] 记录矩阵 [0, 0, i, j] 的元素和
    vector<vector<int>> preSum;

public:
    NumMatrix(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        if(m == 0 || n == 0) return;

        // 构造前缀和矩阵
        preSum = vector<vector<int>>(m+1, vector<int>(n+1, 0));

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                // 计算每个矩阵 [0, 0, i, j] 的元素和
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i-1][j-1] - preSum[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) 
    {
        return preSum[row2+1][col2+1] - preSum[row1][col2+1] - preSum[row2+1][col1] + preSum[row1][col1];
}
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */



